package gui;

import java.awt.Font;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.Enumeration;

import javax.swing.AbstractButton;
import javax.swing.ButtonGroup;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JRadioButton;
import javax.swing.UIManager;
//此类实现输出两个景点间的最短路径和最短距离
public class ShortestPath extends JFrame {
	private JPanel shortestPathPanel;

	public ShortestPath() {
		super("求最短路径");
		setSize(1000, 700);
		setLocation(400, 150);

		Font font = new Font("宋体", Font.PLAIN, 25);
		UIManager.put("OptionPane.font", font);
		UIManager.put("OptionPane.messageFont", font);
		UIManager.put("OptionPane.buttonFont", font);

		setVisible(true);
	}
	//实例化一个scenic对象
	function.Scenic scenic = new function.Scenic();
	//得到景点个数
	int scenicAmount=scenic.getTotalNumber();
	function.AdjacencyMatrix am = new function.AdjacencyMatrix(scenicAmount);

	public void shortestPathPanel() {
		shortestPathPanel = new JPanel();
		shortestPathPanel.setLayout(null);
		//将所有景点以按钮的形式在界面显示出来用于方便用户选择起点
		JLabel informationLabel1 = new JLabel("起点:");
		informationLabel1.setBounds(50, 50, 200, 50);
		informationLabel1.setFont(new Font("宋体", Font.PLAIN, 25));
		shortestPathPanel.add(informationLabel1);

		ButtonGroup group0 = new ButtonGroup();
		ArrayList<String> list = scenic.display();
		for (int i = 0; i < list.size(); i++) {
			JRadioButton rb = new JRadioButton(list.get(i), true);
			rb.setBounds(50, 100 + 30 * i, 200, 30);
			rb.setFont(new Font("宋体", Font.PLAIN, 25));
			shortestPathPanel.add(rb);
			group0.add(rb);
		}
		//将所有景点以按钮的形式在界面显示出来用于方便用户选择终点
		JLabel informationLabel2 = new JLabel("终点:");
		informationLabel2.setBounds(250, 50, 200, 50);
		informationLabel2.setFont(new Font("宋体", Font.PLAIN, 25));
		shortestPathPanel.add(informationLabel2);

		ButtonGroup group1 = new ButtonGroup();
		ArrayList<String> list1 = scenic.display();
		for (int i = 0; i < list1.size(); i++) {
			JRadioButton rb = new JRadioButton(list1.get(i), true);
			rb.setBounds(250, 100 + 30 * i, 200, 30);
			rb.setFont(new Font("宋体", Font.PLAIN, 25));
			shortestPathPanel.add(rb);
			group1.add(rb);
		}
		//informationLabel用于在界面上显示计算出的最短路径长度以及最短路径
		JLabel informationLabel = new JLabel("");
		informationLabel.setBounds(500, 50, 400, 400);
		informationLabel.setFont(new Font("宋体", Font.PLAIN, 25));
		shortestPathPanel.add(informationLabel);
		//用户选择好起点和终点后点击输出按钮即可在界面打印出对应的最短路径长度以及最短路径
		JButton button = new JButton("输出");
		button.setBounds(270, 520, 100, 40);
		button.setFont(new Font("宋体", Font.PLAIN, 25));
		shortestPathPanel.add(button);
		button.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent e) {
				int enable1 = 0;
				//获取buttongroup中选中按钮的文本
				Enumeration<AbstractButton> radioBtns = group0.getElements();
				AbstractButton btn;
				while (radioBtns.hasMoreElements()) {
					btn = radioBtns.nextElement();
					if (btn.isSelected()) {
						enable1 = Integer.parseInt(btn.getText().split(" ")[0]);
						break;
					}
				}

				int enable2 = 0;
				//获取buttongroup中选中按钮的文本
				Enumeration<AbstractButton> radioBtns2 = group1.getElements();
				AbstractButton btn2;
				while (radioBtns2.hasMoreElements()) {
					btn2 = radioBtns2.nextElement();
					if (btn2.isSelected()) {
						enable2 = Integer.parseInt(btn2.getText().split(" ")[0]);
						break;
					}
				}
				//若用户选择的起点和终点为同一个景点，提示用户
				if(enable1==enable2) {
					JOptionPane.showMessageDialog(null, "起点和终点不能是同一个景点哦!", "提示", JOptionPane.ERROR_MESSAGE);
				} else {
//					调用shortestPath方法进行计算
					String information=shortestPath(enable1-1, enable2-1);
					informationLabel.setText(information);
				}
			}
		});

		shortestPathPanel.setVisible(true);
		add(shortestPathPanel);
		setVisible(true);
	}

	//Dijkstra算法
	private String shortestPath(int source, int destination) {
		//构建景点邻接矩阵
		am.create();
		int MAX_VALUE = 32767;
		// scenicAmount为图中顶点个数
		// 保存最短路径长度数组
		int[] dist = new int[scenicAmount];
		// 保存最短路径上的前驱顶点
		int[] path = new int[scenicAmount];
		// 保存此景点是否已被加入最短路径中
		boolean[] set = new boolean[scenicAmount];

		for (int i = 0; i < scenicAmount; i++) {
			dist[i] = am.get(source, i); // dist数组初始化
			set[i] = false;//set数组初始化
			// path数组初始化
			if (i != source && dist[i] < MAX_VALUE)
				path[i] = source;
			else
				path[i] = -1; 
		}
		// 将起点加入最短路径
		set[source] = true;
		dist[source] = 0; 
		// 选择当前不在集合set中具有最短路径的顶点u
		for (int i = 0; i < scenicAmount - 1; i++) {
			//min用于记录最短路径的长度
			int min = MAX_VALUE;
			int u = source;
			for (int j = 0; j < scenicAmount; j++)
				if (!set[j] && dist[j] < min) {
					u = j;
					min = dist[j];
				}
			set[u] = true; // 将顶点u加入集合set
			for (int w = 0; w < scenicAmount; w++) // 每加入一个顶点更新一次dist数组和path数组
				if (!set[w] && am.get(u, w) < MAX_VALUE && dist[u] + am.get(u, w) < dist[w]) {
					dist[w] = dist[u] + am.get(u, w);
					path[w] = u;
				}
		}
//	构建information用于在界面打印计算结果
		String information = "<html><body>该路径长度："+Integer.toString(dist[destination]);	
		information+="<br/>最短路径："+"<br/>"+scenic.findNameByNumber(source)+"<br/>";
		int p=destination;
		String[] route=new String[scenicAmount];
		int x=0;
		//从终点回溯到起点回溯出最短路径
		while(path[p]!= source) {
			route[x]=scenic.findNameByNumber(path[p]);
			x++;
			p=path[p];
		}
		for(int i=x-1;i>=0;i--) {			
			information +=(route[i]+"<br/>");
		}
		information += scenic.findNameByNumber(destination)+"</body></html>";
		return information;
	}
	
	
}
